package PersonStu.sanqi;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @Author: Dijah
 * @Date: 2022/10/27 14:42
 * @Desc:
 * 给定一个由字符串组成的数组 String[]strs，给定一个正数K
 * 返回词频最大的前k个字符串，假设结果是唯一的
 *
 * 思路：
 * 先用一个hash表，记录每个词频的频率。
 * 将每一个hash表封装成一个小的数据项，放到小根堆中。弹出前k个
 */
public class code_06_TopTimes {

    public static class Node{
        public String str;
        public int times;

        public Node(String str, int times) {
            this.str = str;
            this.times = times;
        }

    }

    //构建小根堆
    public static class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1,Node o2) {
            return o1.times - o2.times;
        }
    }


    public static void printTopKAndRank(String [] arr,int topK){
        if(arr == null || arr.length == 0 || topK < 1 || topK > arr.length){
            return;
        }
        //放到map中。
        HashMap<String , Integer> map = new HashMap<>();
        for (String str : arr) {
            if(!map.containsKey(str)){
                map.put(str,1);
            }else {
                map.put(str,map.get(str) + 1);
            }
        }
        //相当于上面的判断   topK > arr.length
//        topK = Math.min(topK,arr.length);
        //将map放到小根堆中
        PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            Node cur = new Node(entry.getKey(),entry.getValue());
            if(heap.size() < topK){
                //加到小根堆中
                heap.add(cur);
            }else {
                //堆满了
                if(heap.peek().times < cur.times){
                    //如果堆顶的次数小于当前的次数，那么将堆顶的弹出，将现在的加到堆顶
                    heap.poll();
                    heap.add(cur);
                }
            }
        }
        while (!heap.isEmpty()){
            System.out.println(heap.poll().str);
        }
    }
    public static void main(String[] args) {
        String[] arr1 = { "K","L", "M", "L", "C", "L", "C", "M", "M" };
        printTopKAndRank(arr1, 3);
    }

}
